1. Field of the Invention
The present invention relates to computer-aided design of integrated circuits wherein circuit entities, or "cells", are placed on an integrated circuit layout and interconnected using computer design layout tools. In particular, the invention relates to "weighted-net" placement methods in which placement is influenced by weights assigned to interconnections between cells.
2. State of the Art
Design layout of integrated circuits has quickly progressed from a uniquely human endeavor to one that is human-directed but, to a large extent, machineimplemented. Design houses rely heavily on design layout tools to produce accurate, efficient designs in a small amount of time. Given a netlist description of an integrated circuit, the task of such tools is to place circuit modules on a layout of the integrated circuit and to route interconnections between the modules so as to achieve a compact layout without violating any design rules, which protect the functional integrity of the integrated circuit. Fully automatic layout systems for custom VLSI integrated circuits are presently available. Examples of such systems (followed in parenthesis by the university at which they were developed) are the PI system (Massachusetts Institute of Technology), the Magic system (University of California at Berkeley), the Phoenix system (Stanford) and the Timberwolf system (University of California at Berkeley). The PI system is named for the two principal parts of the layout problem, namely placement and interconnection (routing). The present invention is concerned only with placement and in particular preplacement, in which the placement of certain circuit entities is dictated or heavily influenced by some a priori information, possibly from the circuit designer.
The PI system is described in detail in Sherman, VLSI Placement and Routing: the PI Project (Springer-Verlag, 1989). Placement in the PI system uses a method known as "min-cut", a placement technique based on graph partitioning methods. Starting with a group of cells to be placed into a rectangular area, the area is divided into two equal areas either vertically or horizontally with the objective of dividing the cells into two approximately equal size groups such that the number of signals that cross the cutline between the two groups is minimized. This process is first applied to all the cells to be placed and is then successively repeated on each of the groups until each group contains less than the specified number of cells. Min-cut placement is illustrated in FIGS. 1A-1D. Modules are displayed as black rectangular regions. Whenever two or more modules overlap, however, regions with an even number of overlapping modules are displayed in white, and regions with an odd number of overlapping modules are displayed in black. In FIG. 1A, the first step of the min-cut process has partitioned the logic modules into two subsets and has sliced the logic box into two rectangles. The modules associated with each of the newly created rectangles are displayed at the origin of their associated rectangle. In FIG. 1B, the modules on the left side of the logic box have been partitioned into two subsets, and the associated rectangle has been sliced into two rectangles. In FIG. 1C, the modules on the right side of the logic box have been partitioned using a horizontal partition. At the conclusion of one version of the min-cut process, each module is associated with a unique leaf rectangle in the recursive slicing as shown in FIG. 1D.
Another placement method based on recursive slicing uses a slicing tree representation of module placement. A "slicing structure" is a rectangle dissection that can be obtained by recursively cutting rectangles into smaller rectangles. A "slicing tree" is a top down description of a slicing structure. It specifies how a given rectangle is cut into smaller rectangles by horizontal and vertical cutting lines. Referring to FIG. 2, each module is labelled with an integer number, or operand, and the operators + and * represent horizontal and vertical cuts, respectively. Each slicing structure may be represented by either a slicing tree or a corresponding "normalized Polish expression" of specified form. In FIG. 2, both the slicing tree and its corresponding normalized Polish expression appear next to the top-most slicing structure. Only the normalized Polish expression appears next to the remaining slicing structures.
In practice, the modules are initially assumed to be placed all horizontally next to one another, usually far from the optimal solution. By manipulating the corresponding normalized Polish expression, random moves are tried as shown in FIG. 2. Two adjacent operators may be swapped (move M1), an operand chain may be complemented (move M2), or an operand and an operator that are adjacent to one another may be swapped. For placement of general cells, which may have different sizes and shapes (as opposed to standard cells which have substantially uniform heights and are placed in rows), slicing tree placement is probably preferrable to min-cut placement.
In the Timberwolf system, placement is based on a method known as simulated annealing, a general-purpose optimization technique inspired by the physical annealing process. Starting with some arbitrary initial placement, a new placement is randomly generated by a perturbation to the current placement. If the new placement is better than the old placement as determined in accordance with a predefined cost function, then the new placement is accepted and replaces the old placement. If the new placement is inferior, the new placement may still be accepted depending on the "temperature" of the system. The temperature of the system is initially set to some large value and is progressively reduced in accordance with a "cooling schedule". If a large number of placements are generated at each temperature and the temperature is very slowly reduced, then simulated annealing may be expected to produce solutions with near-optimal values of the cost function.
Often during the design process, the circuit designer may wish to dictate or at least heavily influence the placement of a particular cell or module. Simulated annealing is very amenable to preplacement. In essence, the designer may simply specify that the cell occupy the desired position in the initial placement and not allow the cell to be moved during the simulated annealing process. Preplacement is also easily accommodated using a quadratic placement method. In general, placement methods that first do relative placement in space and then perform unoverlap and packing to obtain the final position of the cells can incorporate preplacement in the method by simply fixing the preplaced cells in space. Such placement algorithms, however, consume a large amount of computer time.
Min-cut and other similar placement methods are much faster than the foregoing class of algorithms. Preplacement however, is difficult. In general, cell placement algorithms involving iterative operations on a slice tree built from the cells make preplacement difficult. Preplacement using such algorithms has typically been attempted by, at each level of the iterative placement process, dictating with respect to a particular module a partial placement solution that is consistent with its ultimate desired placement. Such a method is inelegant and tedious.
What is needed, then, is a preplacement method that may be incorporated into design tools that find preplacement difficult.